Recently, LDPC (Low Density Parity Check) codes, which have been reported to achieve excellent performance approaching a Shannon limit, which is a theoretical limit of code performance, are used for cellular phones and wireless LANs, etc. as an error correcting code. While the LDPC codes being used in cellular phones etc. are binary LDPC codes, it is known that non-binary LDPC codes constructed over an extended Galois field have higher decoding performance than that of the binary LDPC codes for short code lengths not more than 10,000 bits, such as several hundreds to several thousands bits. In particular, the decoding processing of non-binary LDPC encoded data can be efficiently performed by using a SUM-PRODUCT algorithm (SPA) which allows the use of parallel calculation.
In the SPA decoding processing, multiplication processing at a variable node and convolution operation processing at a check node are repeated. However, since in the SPA decoding processing of non-binary LDPC codes, complex convolution operation processing needs to be performed at the check node which is at a higher order than that of the variable node, there has been a problem that the processing speed decreases.
While, for this purpose, an algorithm for performing convolution operation at high speed by using FFT (Fast Fourier Transform) has been proposed, the execution of the algorithm requires high operational accuracy. Moreover, an algorithm for approximating and simplifying the convolution operation processing at a check node is disclosed. However, even if this algorithm is used, the convolution operation processing at a check node is still time consuming processing, and increasing the processing speed has not been easy.